`:top

`t

| perfekter Graph |

|---|

| |

| Beispiele: |

| Chordale Graphen Bipartite Graphen Vollständige Graphen Co-Graphen Vergleichbarkeitsgraphen |

`t

In der `F33f`_`[Graphentheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graphentheorie]`_`f heißt ein `F33f`_`[Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f `!perfekt`!, wenn für jeden `F33f`_`[induzierten Subgraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Induzierter_Teilgraph]`_`f gilt, dass seine `F33f`_`[Cliquenzahl`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Cliquenzahl]`_`f mit seiner `F33f`_`[chromatischen Zahl`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Chromatische_Zahl]`_`f übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der `F33f`_`[Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knoten_(Graphentheorie)]`_`f und allen `F33f`_`[inzidenten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Inzidenz_(Graphentheorie)]`_`f `F33f`_`[Kanten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kante_(Graphentheorie)]`_`f.

>>Contents

• `F0af`_`[Eigenschaften`#eigenschaften]`_`f

• `F0af`_`[Sätze über perfekte Graphen`#s-tze-ber-perfekte-graphen]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Weblinks`#weblinks]`_`f

• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f

-─

>>Eigenschaften

In einem perfekten Graphen können chromatische Zahl, Cliquenzahl und `F33f`_`[Stabilitätszahl`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Stabilitätszahl]`_`f in polynomieller `F33f`_`[Laufzeit`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Laufzeit_(Informatik)]`_`f berechnet werden,`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] deren Berechnung auf allgemeinen Graphen `F33f`_`[NP-vollständig`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=NP-vollständig]`_`f ist. Es kann in polynomieller Zeit bestimmt werden, ob ein Graph perfekt ist.`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f] Beispiele für perfekte Graphen sind `F33f`_`[bipartite Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bipartiter_Graph]`_`f, `F33f`_`[Kantengraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kantengraph]`_`f bipartiter Graphen und deren Komplemente. Sie bilden die Basis für den starken perfekten Graphensatz und werden daher in diesem Zusammenhang auch als `!einfache perfekte Graphen`! bezeichnet. Weitere Beispiele für perfekte Graphen sind `F33f`_`[chordale Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Chordale_Graphen]`_`f und `F33f`_`[chordal bipartite Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Chordal_bipartiter_Graph]`_`f.

Nach dem `!Satz über perfekte Graphen`! sind folgende Aussagen äquivalent:

1. `* G {\\displaystyle G} `* ist ein perfekter `F33f`_`[Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f.

2. Der `F33f`_`[Komplementgraph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Komplementgraph]`_`f von `* G {\\displaystyle G} `* ist perfekt.

3. Weder `* G {\\displaystyle G} `* selbst noch sein `F33f`_`[Komplementgraph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Komplementgraph]`_`f enthält einen ungeraden `F33f`_`[Zyklus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Zyklus_(Graphentheorie)]`_`f der Länge mindestens 5 als induzierten `F33f`_`[Teilgraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Teilgraph]`_`f. Graphen mit dieser Eigenschaft heißen `!Berge-Graphen`!.

Die zweite Charakteristik ist als `!schwacher Perfekte-Graphen-Satz`! bekannt, wurde schon 1972 von `F33f`_`[László Lovász`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=László_Lovász]`_`f bewiesen und wird deshalb nun `F33f`_`[Satz von Lovász`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_von_Lovász]`_`f genannt. Die dritte Charakteristik ist auch als `!starker Perfekte-Graphen-Satz`! bekannt und wurde erst im Mai 2002 bewiesen.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f] Beide Aussagen wurden schon 1960 von `F33f`_`[Claude Berge`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Claude_Berge]`_`f als Vermutung aufgestellt.

>>Sätze über perfekte Graphen

In allen `F33f`_`[Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f stellt die `F33f`_`[Cliquenzahl`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Cliquenzahl]`_`f eine Untergrenze für die chromatische Zahl dar, da allen `F33f`_`[Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knoten_(Graphentheorie)]`_`f in einer `F33f`_`[Clique`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Clique_(Graphentheorie)]`_`f in jeder richtigen Farbe unterschiedliche Farben zugewiesen werden müssen. Die perfekten Graphen sind diejenigen, für die diese Untergrenze fest ist, nicht nur im Graphen selbst, sondern in allen induzierten `F33f`_`[Teilgraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Teilgraph]`_`f. Bei Graphen, die nicht perfekt sind, können sich die chromatische Zahl und die Cliquenzahl unterscheiden. Zum Beispiel erfordert ein `F33f`_`[Zyklus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Zyklus_(Graphentheorie)]`_`f der Länge fünf drei Farben in jeder `F33f`_`[Färbung`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Färbung_(Graphentheorie)]`_`f, aber seine größte Clique hat die Größe zwei.

Ein Beweis dafür, dass eine Klasse von `F33f`_`[Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f perfekt ist, kann als `F33f`_`[Min-Max-Theorem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Min-Max-Theorem]`_`f angesehen werden: Die minimale Anzahl von Farben, die für diese Graphen benötigt wird, entspricht der maximalen Größe einer `F33f`_`[Clique`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Clique_(Graphentheorie)]`_`f. Viele wichtige Min-Max-Theoreme in der `F33f`_`[Kombinatorik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kombinatorik]`_`f können mit diesen Begriffen ausgedrückt werden.

Zum Beispiel besagt der `F33f`_`[Satz von Dilworth`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_von_Dilworth]`_`f, dass die minimale Anzahl von Ketten in einer Partition einer `F33f`_`[Halbordnung`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Halbordnung]`_`f in Ketten der maximalen Größe einer `F33f`_`[Antikette`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Antikette]`_`f entspricht und so umformuliert werden kann, dass die `F33f`_`[Komplementgraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Komplementgraph]`_`f von `F33f`_`[Vergleichbarkeitsgraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Vergleichbarkeitsgraph]`_`f perfekt sind. Der Satz von Mirsky besagt, dass die minimale Anzahl von Antiketten in einer Partition in Antiketten der maximalen Größe einer Kette entspricht und in gleicher Weise der Perfektion von Vergleichbarkeitsgraphen entspricht.

Die Perfektion von Permutationsgraphen entspricht der Aussage, dass in jeder Folge von geordneten Elementen die Länge der längsten aufsteigenden `F33f`_`[Teilfolge`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Teilfolge]`_`f der minimalen Anzahl von Folgen in einer Partition in aufsteigende Teilfolgen entspricht. Der Satz von Erdős-Szekeres ist eine einfache Folgerung aus dieser Aussage.

Der `F33f`_`[Satz von König`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_von_König_(Graphentheorie)]`_`f besagt, dass eine minimale `F33f`_`[Knotenüberdeckung`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knotenüberdeckung]`_`f in einem `F33f`_`[bipartiten Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bipartiter_Graph]`_`f einem `F33f`_`[maximalen Matching`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Maximales_Matching]`_`f entspricht und umgekehrt. Es kann als die Perfektion der `F33f`_`[Komplementgraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Komplementgraph]`_`f von bipartiten Graphen interpretiert werden. Ein anderer Satz über bipartite Graphen, dass ihr `F33f`_`[chromatischer Index`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Chromatischer_Index]`_`f ihrem maximalen `F33f`_`[Knotengrad`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knotengrad]`_`f entspricht, entspricht der Perfektion der `F33f`_`[Kantengraphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kantengraph]`_`f von bipartiten Graphen.

Der `F33f`_`[schwache Perfekte-Graphen-Satz`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Schwacher_Perfekte-Graphen-Satz]`_`f von `F33f`_`[László Lovász`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=László_Lovász]`_`f besagt, dass ein `F33f`_`[Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f genau dann perfekt ist, wenn sein `F33f`_`[Komplementgraph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Komplementgraph]`_`f perfekt ist. Somit entspricht die Perfektion eines Graphen definiert als die Gleichheit der maximalen Cliquengröße und der chromatischen Zahl in jedem induzierten Teilgraphen der Aussage, dass die Größe einer maximalen `F33f`_`[unabhängigen Menge`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Unabhängige_Menge]`_`f gleich der Cliquenüberdeckungszahl ist.`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f]`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f]

Der starke Perfekte-Graphen-Satz von Chudnovsky, Robertson, Seymour und Thomas liefert eine andere Charakterisierung perfekter Graphen. Ein induzierter `F33f`_`[Zyklus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Zyklus_(Graphentheorie)]`_`f mit einer ungeraden Länge von mindestens 5 wird als `*ungerades Loch`* bezeichnet. Ein induzierter Teilgraph, der der `F33f`_`[Komplementgraph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Komplementgraph]`_`f eines ungeraden Lochs darstellt, wird als `*ungerades Antiloch`* bezeichnet. Ein ungerader Zyklus mit einer Länge von mehr als 3 kann nicht perfekt sein, da seine chromatische Zahl drei und seine `F33f`_`[Cliquenzahl`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Cliquenzahl]`_`f zwei ist. In ähnlicher Weise kann der Komplementgraph eines ungeraden Zyklus der Länge `* 2 ⋅ ⋅ k + 1 {\\displaystyle 2\\cdot k+1} `* nicht perfekt sein, da seine chromatische Zahl `* k + 1 {\\displaystyle k+1} `* und seine Cliquenzahl `* k {\\displaystyle k} `* ist. Alternativ folgt dies aus dem `F33f`_`[Perfekte-Graphen-Satz`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Schwacher_Perfekte-Graphen-Satz]`_`f und daraus, dass der komplementäre ungerade Zyklus nicht perfekt ist. Weil diese Graphen nicht perfekt sind, muss jeder perfekte Graph ein Berge-Graph sein, ein Graph ohne ungerade Löcher und ohne ungerade Antilöcher.`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f]

>>Literatur

• `F33f`_`[Vašek Chvátal`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Vašek_Chvátal]`_`f: `*Perfect Problems`*. über Perfekte Graphen.

• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: `*Exakte Algorithmen für schwere Graphenprobleme`*. Springer-Verlag, Berlin / Heidelberg 2010, ISBN 978-3-642-04499-1

>>Weblinks

• `*perfect`* – Eintrag im Information System on Graph Classes and their Inclusions

• `*Berge`* – Eintrag im Information System on Graph Classes and their Inclusions

>>Einzelnachweise

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `F33f`_`[Grötschel`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Martin_Grötschel]`_`f, `F33f`_`[Lovász`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=László_Lovász]`_`f, `F33f`_`[Alexander Schrijver`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Alexander_Schrijver]`_`f: `*Geometric Algorithms and Combinatorial Optimization`*. Springer-Verlag, 1988, Kapitel 9, `*Stable Sets in Graphs`*, S. 273–303

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `F33f`_`[Chudnovsky`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Maria_Chudnovsky]`_`f, Cornuéjols, Liu, `F33f`_`[Seymour`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Paul_Seymour_(Mathematiker)]`_`f, Vušković: `*Recognizing Berge Graphs`*. In: `*Combinatorica`*, Bd. 25, Nr. 2, 2005, S. 143–186

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `F33f`_`[Chudnovsky`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Maria_Chudnovsky]`_`f, `F33f`_`[Robertson`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Neil_Robertson_(Mathematiker)]`_`f, `F33f`_`[Seymour`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Paul_Seymour_(Mathematiker)]`_`f, `F33f`_`[Thomas`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Robin_Thomas_(Mathematiker)]`_`f: `*The strong perfect graph theorem`*. In: `*Annals of Mathematics`*, Bd. 164, 2006, S. 51–229

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f `F33f`_`[Lovász, László`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=László_Lovász]`_`f: A characterization of perfect graphs. In: Journal of Combinatorial Theory. 13. Jahrgang, Nr. 2, 1972, S. 95–98, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1016/0095-8956(72)90045-7.

`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f `F33f`_`[Lovász, László`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=László_Lovász]`_`f: Perfect graphs. In: Academic Press. 1983, S. 55–87.

`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: The strong perfect graph theorem. In: `F33f`_`[Annals of Mathematics`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Annals_of_Mathematics]`_`f. 164. Jahrgang, Nr. 1, 2006, S. 51–229, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.4007/annals.2006.164.51, `F33f`_`[arxiv`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=ArXiv]`_`f:math/0212070 (princeton.edu).

`c`F0af`_`[↑ Back to top`#top]`_`f`a